Search results for "Neighborhood search"

Large multiple neighborhood search for the soft-clustered vehicle-routing problem

2021

Abstract The soft-clustered vehicle-routing problem (SoftCluVRP) is a variant of the classical capacitated vehicle-routing problem. Customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. In this paper, we present a large multiple neighborhood search for the SoftCluVRP. We design and analyze multiple cluster destroy and repair operators as well as two post-optimization components, which are both based on variable neighborhood descent. The first allows inter-route exchanges of complete clusters, while the second searches for intra-route improvements by combining classical neighborhoods (2-opt, Or-opt, double-bridge) and the Balas-Simo…

Iterated greedy with variable neighborhood search for a multiobjective waste collection problem

2020

Abstract In the last few years, the application of decision making to logistic problems has become crucial for public and private organizations. Efficient decisions clearly contribute to improve operational aspects such as cost reduction or service improvement. The particular case of waste collection service considered in this paper involves a set of economic, labor and environmental issues that translate into difficult operational problems. They pose a challenge to nowadays optimization technologies since they have multiple constraints and multiple objectives that may be in conflict. We therefore need to resort to multiobjective approaches to model and solve this problem, providing efficie…

Improving the performance of embedded systems with variable neighborhood search

2017

Graphical abstractDisplay Omitted Embedded systems have become an essential part of our lives, mainly due to the evolution of technology in the last years. However, the power consumption of these devices is one of their most important drawbacks. It has been proven that an efficient use of the memory of the device also improves its energy performance. This work efficiently solves the dynamic memory allocation problem, which can be formally defined as follows: given a program that has to be executed by a circuit, the objective is to fit that program in memory in such a way that the computing time required to execute it is minimized. In this work, we propose a parallel variable neighborhood se…

Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem

2019

In the dial-a-ride problem, user-specified transport requests from origin to destination points have to be served by a fleet of homogeneous vehicles. The problem variant we consider aims at finding a set of minimum-cost routes satisfying constraints on vehicle capacity, time windows, maximum route duration, and maximum user ride times. We propose an adaptive large neighborhood search (ALNS) for its solution. The key novelty of the approach is an exact amortized constant-time algorithm for evaluating the feasibility of request insertions in the repair steps of the ALNS. In addition, we use two optional improvement techniques: a local-search-based intraroute improvement of routes of promisin…

Routing electric vehicles with a single recharge per route

2020

Networks : an international journal (2020). doi:10.1002/net.21964

An evolutionary restricted neighborhood search clustering approach for PPI networks

2014

Protein-protein interaction networks have been broadly studied in the last few years, in order to understand the behavior of proteins inside the cell. Proteins interacting with each other often share common biological functions or they participate in the same biological process. Thus, discovering protein complexes made of a group of proteins strictly related can be useful to predict protein functions. Clustering techniques have been widely employed to detect significant biological complexes. In this paper, we integrate one of the most popular network clustering techniques, namely the Restricted Neighborhood Search Clustering (RNSC), with evolutionary computation. The two cost functions intr…

An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle-Routing Problem with Time Windows

2008

This paper presents a new deterministic annealing metaheuristic for the fleet size and mix vehicle-routing problem with time windows. The objective is to service, at minimal total cost, a set of customers within their time windows by a heterogeneous capacitated vehicle fleet. First, we motivate and define the problem. We then give a mathematical formulation of the most studied variant in the literature in the form of a mixed-integer linear program. We also suggest an industrially relevant, alternative definition that leads to a linear mixed-integer formulation. The suggested metaheuristic solution method solves both problem variants and comprises three phases. In Phase 1, high-quality init…

Variable Neighborhood Search for the Vertex Separation Problem

2012

The vertex separation problem belongs to a family of optimization problems in which the objective is to nd the best separator of vertices or edges in a generic graph. This optimization problem is strongly related to other well-known graph problems; such as the Path-Width, the Node Search Number or the Interval Thickness, among others. All of these optimization problems are NP-hard and have practical applications in VLSI, computer language compiler design or graph drawing. Up to know, they have been generally tackled with exact approaches, presenting polynomial-time algorithms to obtain the optimal solution for speci c types of graphs. However, in spite of their practical applications, these…

A parallel variable neighborhood search approach for the obnoxious p -median problem

2018

Heuristics for the Bi-Objective Diversity Problem

2018

Abstract The Max-Sum diversity and the Max-Min diversity are two well-known optimization models to capture the notion of selecting a subset of diverse points from a given set. The resolution of their associated optimization problems provides solutions of different structures, in both cases with desirable characteristics. They have been extensively studied and we can find many metaheuristic methodologies, such as Greedy Randomized Adaptive Search Procedure, Tabu Search, Iterated Greedy, Variable Neighborhood Search, and Genetic algorithms applied to them to obtain high quality solutions. In this paper we solve the bi-objective problem in which both models are simultaneously optimized. No pre…